from Crypto.Util.number import long_to_bytes

c = 845383077442730894956745850475894173050402963378356553406655873101668024718019472074595894224176795441342981424513835305792477122471836494793564049800849091101408745740165957877085710018389836613202772378608360535349154778479446872966696616428976492170784666712723177953998199081074229192588936217416824922266371143673285335049756338598900768015542422109942481081855692828250390287533122097800259816968653352229687611032719705968695189278234011284173784539648272386094679396109821646995557344429543367255947040914513635664397454319131990457985098109804067946310649988270433369208200701227863071945824985701722262392
PP = 18315367552236495632510490638893058316957201738827950951686026458789228918293089041604988139042491896824617883326602982174539446096748993950930581908611291651024032227914288481314258077124644658976051852519822767204451664075945144680024754858400371484670172049322276834606284488186849036384241560795083546611005925885696013773207393906015393482047548058198267188313079042912749897330852304286041214929219291870834187137281364886569979853491584474412612895588332279713656192803030694608505122499949367161709005592862244532800821659745656450039800551125599731750314320235053555743440041858411948023922621819529837740079
ff = 13094292314035700827550338568566573299411860981221087086674400336714171410656016804688151816408886733600404321503970713221017487755650183286996324243017913118930980936821886547171100597662095625682781239986746699472618656322951904935526801163555483480492207464486386843974058505648622080149203123734372919667040784511214362004096485127389704869149685839012439567859607666031615125527570141039205884653130911198115020407965076220645042645769697647086318250855930532693584138245298945893213880015610244914085118324214888188921648965392016042456249791426095416625645895132546609521961973850058520758315264046941914003858
gg = 12493388005104947846345761605901983701911640380767459876865507900036887846231651787508085061134373870486489098941753636434137742885112950085168605402923916290193561069305458311847356833086237992864756818149163955479733604742139878108033796902707265245443059082446946379992118332238777958678557920163914630997846946737358978664611933623420195734020730073675708035645085397498745025254232817858127029600735958626682678891488994283659273271363445466298583992641311235722191647370633145657687506055407995726558381270295009288256382798170766047492243623673953392791677131101200420043086159387102476379230947135066350917095

F.<x,y> = ZZ[]

f = (31 * x**3 * y + 50 * y**2 + 89 * x - 1000) - ff
g = (97 * y**5 * x**2 + 71 * x**2 + 27 * x + 31 * y + 3131)  - gg

ps = f.resultant(g, x).change_ring(GF(PP)).univariate_polynomial().roots()
qs = f.resultant(g, y).change_ring(GF(PP)).univariate_polynomial().roots()

for p in ps:
    p = int(p[0])
    for q in qs:
        q = int(q[0])
        N = p * q
        e = 0x10001
        phi = (p - 1) * (q - 1)
        d = pow(e, -1, phi)
        m = long_to_bytes(int(pow(c, d, N)))

        print(m)

